package datastructure.Tree;


import java.util.*;

/**
 * Description：二叉树实现类
 * Author: zhangc
 * Date：2017/6/20 21:35
 */
public class BinaryTree<T> implements IBinaryTree<T> {

    private TreeNode<T> head;

    private BinaryTree(TreeNode<T> node) {
        this.head = node;
    }

    private BinaryTree() {
    }

    private static class TreeNode<T> {
        private T value;
        private TreeNode<T> leftChild;
        private TreeNode<T> rightChild;

        TreeNode(T value) {
            this.value = value;
        }
    }

    public static <T> IBinaryTree<T> createBinaryTreeByArrayIndexNoRecursive(List<T> list) {

        List<TreeNode<T>> nodeList = new ArrayList<>();

        for (T aList : list) {
            nodeList.add(new TreeNode<>(aList));
        }
        for (int parentIndex = 0; parentIndex <= (list.size() >> 1) - 1; parentIndex++) {
            nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1);
            if ((parentIndex * 2 + 2) < list.size()) {
                nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2);
            }
        }
        return new BinaryTree<>(nodeList.get(0));
    }

    public static <T> IBinaryTree<T> createBinaryTreeByArray(T[] array) {
        return new BinaryTree<>(createBinaryTreeByArray(array, 0));
    }

    private static <T> TreeNode<T> createBinaryTreeByArray(T[] array, int index) {
        TreeNode<T> head = new TreeNode<>(array[ index ]);
        if (2 * index + 1 < array.length)
            head.leftChild = createBinaryTreeByArray(array, 2 * index + 1);
        if (2 * index + 2 < array.length)
            head.rightChild = createBinaryTreeByArray(array, 2 * index + 2);
        return head;
    }

    public static <T> IBinaryTree<T> createBinaryTreeByArrayIndex(T[] array) {
        int length = array.length;
        int index = 0;
        TreeNode<T> head = new TreeNode<>(array[ 0 ]);
        Queue<TreeNode<T>> queue = new LinkedList<>();
        queue.add(head);
        TreeNode<T> temp;
        while (!queue.isEmpty()) {
            temp = queue.remove();
            if (2 * index + 1 < length) {
                temp.leftChild = new TreeNode<>(array[ 2 * index + 1 ]);
                queue.add(temp.leftChild);
            }
            if (2 * index + 2 < length) {
                temp.rightChild = new TreeNode<>(array[ 2 * index + 2 ]);
                queue.add(temp.rightChild);
            }
            ++index;
        }
        return new BinaryTree<>(head);
    }

    public static <T> IBinaryTree<T> createBinaryTreeNoRecursive(List<T> list) {
        IBinaryTree<T> tree = new BinaryTree<>();
        for (T value : list)
            tree.addNodeToBinaryTree(value);
        return tree;
    }

    public void addNodeToBinaryTree(T value) {
        if (head == null) {
            head = new TreeNode<>(value);
        } else {
            Queue<TreeNode<T>> nodes = new LinkedList<>();
            nodes.add(head);
            TreeNode<T> temp;
            while (!nodes.isEmpty()) {
                temp = nodes.remove();
                if (temp.leftChild == null) {
                    temp.leftChild = new TreeNode<>(value);
                    return;
                }
                nodes.add(temp.leftChild);
                if (temp.rightChild == null) {
                    temp.rightChild = new TreeNode<>(value);
                    return;
                }
                nodes.add(temp.rightChild);
            }
        }
    }


    @Override
    public List<T> preOrderTraverse() {
        List<T> list = new ArrayList<>();
        preOrderTraverse(head, list);
        return list;
    }

    private void preOrderTraverse(TreeNode<T> node, List<T> list) {
        if (node != null) {
            list.add(node.value);
            preOrderTraverse(node.leftChild, list);
            preOrderTraverse(node.rightChild, list);
        }
    }

    // 二叉树的先序非递归遍历
    @Override
    public List<T> preOrderTraverseNoRecursive() {
        List<T> list = new ArrayList<>();
        if (head == null)
            return list;
        Stack<TreeNode<T>> stack = new Stack<>();
        stack.push(head);
        TreeNode<T> temp;
        while (!stack.isEmpty()) {
            temp = stack.pop();
            list.add(temp.value);
            if (temp.rightChild != null)
                stack.push(temp.rightChild);
            if (temp.leftChild != null)
                stack.push(temp.leftChild);
        }
        return list;
    }


    @Override
    public List<T> inOrderTraverse() {
        List<T> list = new ArrayList<>();
        inOrderTraverse(head, list);
        return list;
    }

    private void inOrderTraverse(TreeNode<T> node, List<T> list) {
        if (node != null) {
            inOrderTraverse(node.leftChild, list);
            list.add(node.value);
            inOrderTraverse(node.rightChild, list);
        }
    }

    @Override
    public List<T> inOrderTraverseNoRecursive() {
        if (head == null)
            return null;
        Stack<TreeNode<T>> stack = new Stack<>();
        List<T> list = new ArrayList<>();
        TreeNode<T> node = head;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.add(node);
                node = node.leftChild;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                list.add(node.value);
                node = node.rightChild;
            }
        }
        return list;
    }

    @Override
    public List<T> postOrderTraverse() {
        List<T> list = new ArrayList<>();
        postOrderTraverse(head, list);
        return list;
    }

    // 二叉树的后序 非递归 遍历
    @Override
    public List<T> postOrderTraverseNoRecursive() {
        Stack<TreeNode<T>> stack = new Stack<>();
        LinkedList<T> list = new LinkedList<>();
        TreeNode<T> node = head;

        while (node != null || stack.size() > 0) {
            if (node != null) {
                list.addFirst(node.value);
                stack.push(node);
                node = node.rightChild;
            } else {
                node = stack.pop();
                node = node.leftChild;
            }
        }
        return list;
    }

    private void postOrderTraverse(TreeNode<T> node, List<T> list) {
        if (node != null) {
            postOrderTraverse(node.leftChild, list);
            postOrderTraverse(node.rightChild, list);
            list.add(node.value);
        }
    }

    @Override
    public List<T> levelOrder() {
        List<T> list = new ArrayList<>();
        Queue<TreeNode<T>> queue = new LinkedList<>();
        if (head != null)
            queue.add(head);
        TreeNode<T> temp;
        while (!queue.isEmpty()) {
            temp = queue.remove();
            list.add(temp.value);
            if (temp.leftChild != null)
                queue.add(temp.leftChild);
            if (temp.rightChild != null)
                queue.add(temp.rightChild);
        }
        return list;
    }

    public static void main(String[] args) {
        int i=0;
        while(i < (i++)+1);
        System.out.println(i);
    }
}
